53. Maximum Subarray

Question

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum

1. A subarray is a contiguous part of an array

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Solution 1: Brute Force (TLE)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        maxAns = nums[0]
        for i in range(n):
            subArraySum = 0
            for j in range(i, n):
                subArraySum += nums[j]
                maxAns = max(maxAns, subArraySum)    
        return maxAns

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Kadane’s Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = nums[0]
        currSum = 0
        for i in range(n):
            currSum += nums[i]
            ans = max(ans, currSum)
            if currSum < 0:
                currSum = 0
        return ans

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://www.interviewbit.com/blog/maximum-subarray-sum/

Follow-up: Best Time to Buy and Sell Stock

7. Reverse Integer

Question

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

1. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 2

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Solution 1

class Solution:
    def reverse(self, x: int) -> int:
        u32IntMax = 2**31 - 1
        u32IntMin = -(2**31)
        
        rev = 0
        posV = abs(x)
        while(posV > 0):
            if (rev > (u32IntMax // 10)) or (-rev < (u32IntMin // 10)):
                return 0
            rev = 10*rev + posV%10
            posV //= 10
            
        return rev if x > 0 else -rev

Time Complexity: O(log(N))
Space Complexity: O(1)

Solution 2: Python Style (Cheat)

class Solution:
    def reverse(self, x: int) -> int:
        if x >= 0:
            ans = int(str(x)[::-1])
        else:
            ans = -1*int(str(-x)[::-1])
        isOverflow = ans > (2**31) or ans < (-2**31 - 1)
        return ans if not isOverflow else 0

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://mikeylin.gitbooks.io/leetcode/content/7.html

Follow-up: Reverse Bits